﻿#include "dfa.h"
#include <queue>
#include <algorithm>
#include <iostream>

// 比较运算符
bool Item::operator<(const Item& other) const {
    if (lhs != other.lhs) return lhs < other.lhs;
    if (rhs != other.rhs) return rhs < other.rhs;
    return dotPos < other.dotPos;
}

bool Item::operator==(const Item& other) const {
    return lhs == other.lhs && rhs == other.rhs && dotPos == other.dotPos;
}

// 计算闭包
std::set<Item> closure(
    const std::set<Item>& items,
    const std::map<int, std::vector<std::vector<int>>>& grammar
) {
    std::set<Item> result = items;
    bool added;
    do {
        added = false;
        auto temp = result;
        for (const auto& item : temp) {
            if (item.dotPos < item.rhs.size()) {
                int sym = item.rhs[item.dotPos];
                // 只有文法中存在的非终结符才扩展
                if (grammar.count(sym)) {
                    for (const auto& prod : grammar.at(sym)) {
                        Item newItem{ sym, prod, 0 };
                        if (result.insert(newItem).second) added = true;
                    }
                }
            }
        }
    } while (added);
    return result;
}

// GO 转移
std::set<Item> go(
    const std::set<Item>& items,
    int symbol,
    const std::map<int, std::vector<std::vector<int>>>& grammar
) {
    std::set<Item> nextSet;
    for (const auto& item : items) {
        if (item.dotPos < item.rhs.size() && item.rhs[item.dotPos] == symbol) {
            nextSet.insert({ item.lhs, item.rhs, item.dotPos + 1 });
        }
    }
    return closure(nextSet, grammar);
}

// 构造 DFA
void constructDFA(
    const std::map<int, std::vector<std::vector<int>>>& grammar,
    std::vector<std::set<Item>>& states,
    std::map<std::pair<int, int>, int>& transitionTable
) {
    // 以第一个文法条目的左部作为起始符号
    int startSym = grammar.begin()->first;
    // 初始项目
    Item startItem{ startSym, grammar.at(startSym)[0], 0 };
    states.clear();
    transitionTable.clear();

    states.push_back(closure({ startItem }, grammar));
    std::queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int st = q.front(); q.pop();
        std::map<int, std::set<Item>> trans;
        for (const auto& itm : states[st]) {
            if (itm.dotPos < itm.rhs.size()) {
                int sym = itm.rhs[itm.dotPos];
                trans[sym] = go(states[st], sym, grammar);
            }
        }
        for (const auto& f : trans) {
            int sym = f.first;
            auto nxt = f.second;
            auto it = std::find(states.begin(), states.end(), nxt);
            int nxtId;
            if (it == states.end()) {
                states.push_back(nxt);
                nxtId = states.size() - 1;
                q.push(nxtId);
            }
            else nxtId = std::distance(states.begin(), it);
            transitionTable[{st, sym}] = nxtId;
        }
    }
}

// 打印状态项目集
void printState(int id, const std::set<Item>& items) {
    std::cout << "State " << id << ":\n";
    for (const auto& itm : items) {
        std::cout << "  " << itm.lhs << " -> ";
        for (size_t i = 0; i < itm.rhs.size(); ++i) {
            if (i == itm.dotPos) std::cout << "· ";
            std::cout << itm.rhs[i] << " ";
        }
        if (itm.dotPos == itm.rhs.size()) std::cout << "·";
        std::cout << "\n";
    }
    std::cout << "\n";
}

// 打印 DFA 转移表
void printDFA(const std::map<std::pair<int, int>, int>& transitionTable) {
    std::cout << "State Transition Table:\n";
    for (const auto& it : transitionTable) {
        auto key = it.first;
        int val = it.second;
        std::cout << "From state " << key.first
            << " via " << key.second
            << " to state " << val << "\n";
    }
}
//// 主程序
//int main() {
//    // 定义文法
//    std::map<std::string, std::vector<std::string>> grammar = {
//        {"S'", {"S"}},
//        {"S", {"A"}},
//        {"A", {"aA", "b"}}
//    };
//
//    // 初始项目集
//    std::set<Item> startSet = closure({ {"S'", "S", 0} }, grammar);
//
//    // 状态集合和转移表
//    std::vector<std::set<Item>> states = { startSet };
//    std::map<std::pair<int, char>, int> transitionTable;
//
//    std::queue<int> unprocessedStates;
//    unprocessedStates.push(0);
//
//    // 打印初始状态
//    printState(0, startSet);
//
//    while (!unprocessedStates.empty()) {
//        int currentState = unprocessedStates.front();
//        unprocessedStates.pop();
//
//        std::map<char, std::set<Item>> transitions;
//
//        // 计算当前状态的所有转移
//        for (const auto& item : states[currentState]) {
//            if (item.dotPos < item.rhs.size()) {
//                char symbol = item.rhs[item.dotPos];
//                transitions[symbol] = go(states[currentState], symbol, grammar);
//            }
//        }
//
//        for (const auto& transition : transitions) {
//            char symbol = transition.first;
//            const auto& nextStateSet = transition.second;
//            // 检查是否是新状态
//            auto it = std::find(states.begin(), states.end(), nextStateSet);
//            int nextState;
//
//            if (it == states.end()) {
//                states.push_back(nextStateSet);
//                nextState = states.size() - 1;
//                unprocessedStates.push(nextState);
//                printState(nextState, nextStateSet); // 打印新状态
//            }
//            else {
//                nextState = std::distance(states.begin(), it);
//            }
//
//            transitionTable[{currentState, symbol}] = nextState;
//        }
//    }
//
//    // 输出状态转移表
//    std::cout << "State transition table:\n";
//    for (const auto& items : transitionTable) {
//        std::pair<int, char> key = items.first;
//        int value = items.second;
//        std::cout << "From state " << key.first << " via " << key.second << " to state " << value << "\n";
//    }
//
//    return 0;
//}
